//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
// 
// Related Topics 字符串 动态规划 
// 👍 2653 👎 0

package leetcode.editor.cn;

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Stack;

// Java5: 最长回文子串
public class Q5LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new Q5LongestPalindromicSubstring().new Solution();
//        System.out.println("rs = "+solution.longestPalindrome("babad"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            return my2(s);
        }

        @Deprecated
        public String my(String s) {
            if (s == null) return null;
            if (s.length() <= 1) return s;
            String re = "";
            for (int i=0; i<s.length(); i++) {
                char c = s.charAt(i);
                int j = s.indexOf(c, i+1);
                while (j!=-1) {
                    System.out.println("i: "+i+", j: "+j);
                    int le = i, ri = j;
                    boolean is = true;
                    while (le <= ri-1) {
                        if (s.charAt(le) == s.charAt(ri)) {
                            le = le + 1;
                            ri = ri - 1;
                            continue;
                        } else {
                            is = false;
                            break;
                        }
                    }
                    if (is) {
                        if (re.length() < j-i+1) {
                            re = s.substring(i, j+1);
                        }
                    }
                    j = s.indexOf(c, j+1);
                }
            }
            return re==""?s.substring(0, 1):re;
        }

        public String my2(String s) {
            if (s == null || s.length() <= 1) return s;
            String re = "";
            int i=0;
            while (i < s.length()) {
                int j = i;
                while (j < s.length() && s.charAt(i) == s.charAt(j)) {
                    j++;
                }
                j = j - 1;

//                System.out.println("I: "+i+ ", J: " + j);

                String sub = expand(s, i, j);
//                System.out.println("sub: "+sub);
                if (re.length() < sub.length()) re = sub;
                i = j+1;
            }
            return re;
        }

        private String expand(String s, int i, int j) {
            if (i>=0 && j<s.length() && s.charAt(i) == s.charAt(j)) {
                return expand(s, i-1, j+1);
            } else {
                i = Math.max(i+1, 0);
                j = Math.min(j-1, s.length()-1);
            }
//            System.out.println("I: "+i+ ", J: " + j);
            return s.substring(i, j+1);
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

}

